package algorithm.graph.adjacencymatrix;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Floyd2 {
    AdjacencyMatrixGraph graph;
    List<Integer>[][] transferMatrix;
    int[][] minPathLengthMatrix;

    public Floyd2(AdjacencyMatrixGraph graph) {
        this.graph = graph;
    }

    public void buildPathMatrix() {
        this.transferMatrix = initTransfer(graph.getNodeCount());
        this.minPathLengthMatrix = initPathLength(graph.getNodeCount(), graph.getGraphData());
        int nodeCount = graph.getNodeCount();
        for (int k = 0; k < nodeCount; k++) {
            for (int i = 0; i < nodeCount; i++) {
                for (int j = 0; j < nodeCount; j++) {
                    if (minPathLengthMatrix[i][k] != -1 && minPathLengthMatrix[k][j] != -1) {
                        int newPathLength = minPathLengthMatrix[i][k] + minPathLengthMatrix[k][j];
                        if (minPathLengthMatrix[i][j] == -1 || minPathLengthMatrix[i][j] > newPathLength) {
                            minPathLengthMatrix[i][j] = minPathLengthMatrix[i][k] + minPathLengthMatrix[k][j];
                            transferMatrix[i][j] = new ArrayList<>();
                            transferMatrix[i][j].add(k);
                        } else if (minPathLengthMatrix[i][j] == newPathLength) {
                            transferMatrix[i][j].add(k);
                        }
                    }
                }
            }
        }
    }

    private int[][] initPathLength(int nodeCount, int[][] graphData) {
        int[][] pathLength = new int[nodeCount][nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            for (int j = 0; j < nodeCount; j++) {
                pathLength[i][j] = graphData[i][j];
            }
        }
        return pathLength;
    }

    private List<Integer>[][] initTransfer(int nodeCount) {
        List<Integer>[][] transfer = new List[nodeCount][nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            for (int j = 0; j < nodeCount; j++) {
                transfer[i][j] = new ArrayList<>();
            }
        }
        return transfer;
    }

    public List<List<Integer>> findShortestPath(int from, int to) {
        if (minPathLengthMatrix[from][to] == -1) {
            if (from == to) {
                return List.of(List.of(from));
            } else {
                return List.of();
            }
        } else {
            List<List<Integer>> transferList = findShortestPathSupport(from, to);
            transferList.forEach(it -> {
                it.add(0, from);
                it.add(to);
            });
            return transferList;
        }
    }

    private List<List<Integer>> getCartesianProduct(List<List<Integer>> first, List<List<Integer>> second) {
        if (first.size() == 0 && second.size() == 0) {
            List<List<Integer>> result = new ArrayList<>();
            return result;
        } else if (first.size() == 0 && second.size() != 0) {
            List<List<Integer>> result = new ArrayList<>();
            for (List<Integer> secondPart : second) {
                List<Integer> resultPart = new ArrayList<>();
                resultPart.addAll(secondPart);
                result.add(resultPart);
            }
            return result;
        } else if (first.size() != 0 && second.size() == 0) {
            return getCartesianProduct(second, first);
        } else {
            List<List<Integer>> result = new ArrayList<>();
            for (List<Integer> firstPart : first) {
                for (List<Integer> secondPart : second) {
                    List<Integer> resultPart = new ArrayList<>();
                    resultPart.addAll(firstPart);
                    resultPart.addAll(secondPart);
                    result.add(resultPart);
                }
            }
            return result;
        }
    }

    private List<List<Integer>> findShortestPathSupport(int from, int to) {
        if (transferMatrix[from][to].size() == 0) {
            return List.of();
        } else {
            List<Integer> transferList = transferMatrix[from][to];
            List<List<Integer>> result = new ArrayList<>();
            for (Integer transfer : transferList) {
                List<List<Integer>> leftPartialPathList = findShortestPathSupport(from, transfer);
                List<List<Integer>> transferPartialPathList = Arrays.asList(Arrays.asList(transfer));
                List<List<Integer>> rightPartialPathList = findShortestPathSupport(transfer, to);
                result.addAll(getCartesianProduct(getCartesianProduct(leftPartialPathList, transferPartialPathList), rightPartialPathList));
            }
            return result;
        }
    }
}
